#ifndef TRIE_HPP
#define TRIE_HPP
#include <map>
#include <list>

template<typename elem_t, typename value_t, template<typename k, typename v> class map_t = std::map>
class trie {

  struct node;
  struct _key_iterator;
  template<typename iter_value_t> struct _iterator;
  
  typedef std::map<elem_t, node> mapper_t;
  typedef typename std::list<typename mapper_t::iterator>::iterator _key_iterator_base;

  template<typename iter_value_t> friend class _iterator;

public:

  typedef _key_iterator key_iterator;
  typedef _iterator<value_t> iterator;
  typedef _iterator<const value_t> const_iterator;

private:

  bool own_root_m;
  node* root_m;
  const typename mapper_t::iterator begin_m;
  const typename mapper_t::iterator end_m;

  static node* make_new_root_node();

public:
  
  trie();
  trie(const trie&);
  ~trie();
  trie(const iterator&);
  
  iterator operator*();
  iterator root();
  iterator begin();
  iterator end();

  const_iterator begin() const;
  const_iterator end() const;
  
};


template<typename elem_t, typename value_t, template<typename k, typename v> class map_t>
struct trie<elem_t, value_t, map_t>::node {
  mapper_t trans_m;
  value_t value_m;
  node();
  node(value_t);
  typename mapper_t::iterator get(elem_t);
  typename mapper_t::iterator force(elem_t);
  typename mapper_t::iterator begin();
  typename mapper_t::iterator end();
};

template<typename elem_t, typename value_t, template<typename k, typename v> class map_t>
struct trie<elem_t, value_t, map_t>::_key_iterator : public _key_iterator_base {
  _key_iterator(const _key_iterator_base&);
  const elem_t& operator*() const;
};

template<typename elem_t, typename value_t, template<typename k, typename v> class map_t>
template<typename iter_value_t>
class trie<elem_t, value_t, map_t>::_iterator {
  std::list<typename mapper_t::iterator> prefix_m;
  void advance();
  _iterator& get(elem_t);
  _iterator& force(elem_t);
  bool valid() const;
  friend class trie;
public:
  _iterator();
  _iterator(const typename mapper_t::iterator&);
  _iterator(const _iterator&);
  _iterator& operator=(const _iterator&);
  _iterator& operator=(const trie&);
  
  key_iterator begin();
  key_iterator end();

  bool operator==(const _iterator&) const;
  bool operator!=(const _iterator&) const;
  iter_value_t& operator*();
  iter_value_t* operator->();
  _iterator& operator++();

  _iterator& operator>>(const elem_t&);
  _iterator& operator>(const elem_t&);

  template<typename seq_t> iter_value_t& operator[](const seq_t&);
  template<typename seq_t> _iterator& operator>(const seq_t&);
  template<typename seq_t> _iterator& operator>>(const seq_t&);
  template<typename seq_t> _iterator& insert(const seq_t&, const value_t&);
  template<typename seq_t> _iterator& find(const seq_t&);
  template<typename seq_t> _iterator& force_find(const seq_t&);

  template<typename iter_t> _iterator& insert(const iter_t&, const iter_t&, const value_t&);
  template<typename iter_t> _iterator& find(const iter_t&, const iter_t&);
  template<typename iter_t> _iterator& force_find(const iter_t&, const iter_t&);

  template<typename iter_t> _iterator& insert(const iter_t&, const elem_t&, const value_t&);
  template<typename iter_t> _iterator& find(const iter_t&, const elem_t&);
  template<typename iter_t> _iterator& force_find(const iter_t&, const elem_t&);

};


/* ********************************************************************** *
 * TRIE
 * ********************************************************************** */

template<typename elem_t, typename value_t, template<typename k, typename v> class map_t>
trie<elem_t, value_t, map_t>::trie()
  : own_root_m(true)
  , root_m(make_new_root_node())
  , begin_m(root_m->begin())
  , end_m(root_m->end())
{}

template<typename elem_t, typename value_t, template<typename k, typename v> class map_t>
trie<elem_t, value_t, map_t>::trie(const trie& t)
  : own_root_m(false)
  , root_m(t.root_m)
  , begin_m(t.begin_m)
  , end_m(t.end_m)
{}

template<typename elem_t, typename value_t, template<typename k, typename v> class map_t>
trie<elem_t, value_t, map_t>::trie(const iterator& i)
  : own_root_m(false)
  , root_m(&i.prefix_m.back()->second)
  , begin_m(root_m->begin())
  , end_m(root_m->end())
{}


template<typename elem_t, typename value_t, template<typename k, typename v> class map_t>
trie<elem_t, value_t, map_t>::~trie() {
  if (own_root_m) {
    delete root_m;
  }
}

template<typename elem_t, typename value_t, template<typename k, typename v> class map_t>
inline typename trie<elem_t, value_t, map_t>::node*
trie<elem_t, value_t, map_t>::make_new_root_node() {
  node* n = new node();
  n->trans_m.insert(std::pair<elem_t, node>(elem_t(), node()));
  return n;
}
  
template<typename elem_t, typename value_t, template<typename k, typename v> class map_t>
inline typename trie<elem_t, value_t, map_t>::iterator
trie<elem_t, value_t, map_t>::operator*() {
  return iterator(begin_m);
}

template<typename elem_t, typename value_t, template<typename k, typename v> class map_t>
inline typename trie<elem_t, value_t, map_t>::iterator
trie<elem_t, value_t, map_t>::root() {
  return iterator(begin_m);
}

template<typename elem_t, typename value_t, template<typename k, typename v> class map_t>
inline typename trie<elem_t, value_t, map_t>::iterator
trie<elem_t, value_t, map_t>::begin() {
  return iterator(begin_m);
}

template<typename elem_t, typename value_t, template<typename k, typename v> class map_t>
inline typename trie<elem_t, value_t, map_t>::iterator
trie<elem_t, value_t, map_t>::end() {
  return iterator(end_m);
}

template<typename elem_t, typename value_t, template<typename k, typename v> class map_t>
inline typename trie<elem_t, value_t, map_t>::const_iterator
trie<elem_t, value_t, map_t>::begin() const {
  return const_iterator(begin_m);
}

template<typename elem_t, typename value_t, template<typename k, typename v> class map_t>
inline typename trie<elem_t, value_t, map_t>::const_iterator
trie<elem_t, value_t, map_t>::end() const {
  return const_iterator(end_m);
}



/* ********************************************************************** *
 * NODE
 * ********************************************************************** */

template<typename elem_t, typename value_t, template<typename k, typename v> class map_t>
trie<elem_t, value_t, map_t>::node::node()
  : trans_m()
  , value_m()
{}

template<typename elem_t, typename value_t, template<typename k, typename v> class map_t>
trie<elem_t, value_t, map_t>::node::node(value_t value)
  : trans_m()
  , value_m(value)
{}

template<typename elem_t, typename value_t, template<typename k, typename v> class map_t>
inline typename trie<elem_t, value_t, map_t>::mapper_t::iterator
trie<elem_t, value_t, map_t>::node::get(elem_t key) {
  return trans_m.find(key);
}

template<typename elem_t, typename value_t, template<typename k, typename v> class map_t>
inline typename trie<elem_t, value_t, map_t>::mapper_t::iterator
trie<elem_t, value_t, map_t>::node::force(elem_t key) {
  typename mapper_t::iterator f = trans_m.find(key);
  if (f == trans_m.end()) {
    f = trans_m.insert(std::pair<elem_t, node>(key, node())).first;
  }
  return f;
}

template<typename elem_t, typename value_t, template<typename k, typename v> class map_t>
inline typename trie<elem_t, value_t, map_t>::mapper_t::iterator
trie<elem_t, value_t, map_t>::node::begin() {
  return trans_m.begin();
}

template<typename elem_t, typename value_t, template<typename k, typename v> class map_t>
inline typename trie<elem_t, value_t, map_t>::mapper_t::iterator
trie<elem_t, value_t, map_t>::node::end() {
  return trans_m.end();
}


/* ********************************************************************** *
 * KEY_ITERATOR
 * ********************************************************************** */

template<typename elem_t, typename value_t, template<typename k, typename v> class map_t>
trie<elem_t, value_t, map_t>::_key_iterator::_key_iterator(const _key_iterator_base& base)
  : _key_iterator_base(base)
{}

template<typename elem_t, typename value_t, template<typename k, typename v> class map_t>
inline const elem_t& trie<elem_t, value_t, map_t>::_key_iterator::operator*() const {
  return _key_iterator_base::operator*()->first;
}



/* ********************************************************************** *
 * ITERATOR
 * ********************************************************************** */


template<typename elem_t, typename value_t, template<typename k, typename v> class map_t>
template<typename iter_value_t>
trie<elem_t, value_t, map_t>::_iterator<iter_value_t>::_iterator()
  : prefix_m()
{}

template<typename elem_t, typename value_t, template<typename k, typename v> class map_t>
template<typename iter_value_t>
trie<elem_t, value_t, map_t>::_iterator<iter_value_t>::_iterator(const typename mapper_t::iterator& i)
  : prefix_m()
{
  prefix_m.push_back(i);
}

template<typename elem_t, typename value_t, template<typename k, typename v> class map_t>
template<typename iter_value_t>
trie<elem_t, value_t, map_t>::_iterator<iter_value_t>::_iterator(const _iterator& i)
  : prefix_m(i.prefix_m)
{}

template<typename elem_t, typename value_t, template<typename k, typename v> class map_t>
template<typename iter_value_t>
inline typename trie<elem_t, value_t, map_t>::template _iterator<iter_value_t>&
trie<elem_t, value_t, map_t>::_iterator<iter_value_t>::operator=(const _iterator& i) {
  prefix_m = i.prefix_m;
  return *this;
}

template<typename elem_t, typename value_t, template<typename k, typename v> class map_t>
template<typename iter_value_t>
inline typename trie<elem_t, value_t, map_t>::template _iterator<iter_value_t>&
trie<elem_t, value_t, map_t>::_iterator<iter_value_t>::operator=(const trie& t) {
  prefix_m.clear();
  prefix_m.push_back(t.begin_m);
  return *this;
}

template<typename elem_t, typename value_t, template<typename k, typename v> class map_t>
template<typename iter_value_t>
inline typename trie<elem_t, value_t, map_t>::template _iterator<iter_value_t>&
trie<elem_t, value_t, map_t>::_iterator<iter_value_t>::get(elem_t key) {
  typename mapper_t::iterator i = prefix_m.back()->second.get(key);
  if (i == prefix_m.back()->second.end()) {
    prefix_m.clear();
  } else {
    prefix_m.push_back(i);
  }
  return *this;
}

template<typename elem_t, typename value_t, template<typename k, typename v> class map_t>
template<typename iter_value_t>
inline typename trie<elem_t, value_t, map_t>::template _iterator<iter_value_t>&
trie<elem_t, value_t, map_t>::_iterator<iter_value_t>::force(elem_t key) {
  prefix_m.push_back(prefix_m.back()->second.force(key));
  return *this;
}

template<typename elem_t, typename value_t, template<typename k, typename v> class map_t>
template<typename iter_value_t>
void
trie<elem_t, value_t, map_t>::_iterator<iter_value_t>::advance() {
  typename mapper_t::iterator ext = prefix_m.back()->second.begin();
  while (! prefix_m.empty() && ext == prefix_m.back()->second.end()) {
    ext = prefix_m.back();
    prefix_m.pop_back();
    ++ext;
  }
  prefix_m.push_back(ext);
}

template<typename elem_t, typename value_t, template<typename k, typename v> class map_t>
template<typename iter_value_t>
inline iter_value_t&
trie<elem_t, value_t, map_t>::_iterator<iter_value_t>::operator*() {
  return prefix_m.back()->second.value_m;
}

template<typename elem_t, typename value_t, template<typename k, typename v> class map_t>
template<typename iter_value_t>
inline iter_value_t*
trie<elem_t, value_t, map_t>::_iterator<iter_value_t>::operator->() {
  return &prefix_m.back()->second.value_m;
}

template<typename elem_t, typename value_t, template<typename k, typename v> class map_t>
template<typename iter_value_t>
inline typename trie<elem_t, value_t, map_t>::template _iterator<iter_value_t>&
trie<elem_t, value_t, map_t>::_iterator<iter_value_t>::operator++() {
  advance();
  return *this;
}

template<typename elem_t, typename value_t, template<typename k, typename v> class map_t>
template<typename iter_value_t>
inline bool
trie<elem_t, value_t, map_t>::_iterator<iter_value_t>::valid() const {
  return ! prefix_m.empty();
}

template<typename elem_t, typename value_t, template<typename k, typename v> class map_t>
template<typename iter_value_t>
inline bool
trie<elem_t, value_t, map_t>::_iterator<iter_value_t>::operator==(const _iterator& i) const {
  return prefix_m == i.prefix_m;
}

template<typename elem_t, typename value_t, template<typename k, typename v> class map_t>
template<typename iter_value_t>
inline bool
trie<elem_t, value_t, map_t>::_iterator<iter_value_t>::operator!=(const _iterator& i) const {
  prefix_m != i.prefix_m;
}

template<typename elem_t, typename value_t, template<typename k, typename v> class map_t>
template<typename iter_value_t>
inline typename trie<elem_t, value_t, map_t>::key_iterator
trie<elem_t, value_t, map_t>::_iterator<iter_value_t>::begin() {
  return key_iterator(++prefix_m.begin());
}

template<typename elem_t, typename value_t, template<typename k, typename v> class map_t>
template<typename iter_value_t>
inline typename trie<elem_t, value_t, map_t>::key_iterator
trie<elem_t, value_t, map_t>::_iterator<iter_value_t>::end() {
  return key_iterator(prefix_m.end());
}


/**
 * @name Element access
 */
//@{

/**
 * The forward operator is used to travers the trie.
 * Returns the subtrie in the original trie that shares
 * the supplied element as prefix.
 * If there are no such subtries, an empty trie is returned.
 */
template<typename elem_t, typename value_t, template<typename k, typename v> class map_t>
template<typename iter_value_t>
inline typename trie<elem_t, value_t, map_t>::template _iterator<iter_value_t>&
trie<elem_t, value_t, map_t>::_iterator<iter_value_t>::operator>(const elem_t& key) {
  return get(key);
}

/**
 * The force forward operator is similar to the forward operator,
 * but forces the given element prefix into the original trie.
 * Returns a non-empty trie.
 */
template<typename elem_t, typename value_t, template<typename k, typename v> class map_t>
template<typename iter_value_t>
inline typename trie<elem_t, value_t, map_t>::template _iterator<iter_value_t>&
trie<elem_t, value_t, map_t>::_iterator<iter_value_t>::operator>>(const elem_t& key) {
  return force(key);
}

//@}


/**
 * @name Sequence access
 * The sequence must be iterable (implement a begin() and end() method).
 */
//@{

template<typename elem_t, typename value_t, template<typename k, typename v> class map_t>
template<typename iter_value_t>
template<typename seq_t>
inline iter_value_t&
trie<elem_t, value_t, map_t>::_iterator<iter_value_t>::operator[](const seq_t& seq) {
  return *force_find(seq);
}

/**
 * The forward operator is used to travers the trie.
 * Returns the subtrie in the original trie that shares
 * the supplied sequence as prefix.
 * If there are no such subtries, an empty trie is returned.
 */
template<typename elem_t, typename value_t, template<typename k, typename v> class map_t>
template<typename iter_value_t>
template<typename seq_t>
inline typename trie<elem_t, value_t, map_t>::template _iterator<iter_value_t>&
trie<elem_t, value_t, map_t>::_iterator<iter_value_t>::operator>(const seq_t& seq) {
  return find(seq);
}

/**
 * The force forward operator is similar to the forward operator,
 * but forces the given sequence prefix into the original trie.
 * Returns a non-empty trie.
 */
template<typename elem_t, typename value_t, template<typename k, typename v> class map_t>
template<typename iter_value_t>
template<typename seq_t>
inline typename trie<elem_t, value_t, map_t>::template _iterator<iter_value_t>&
trie<elem_t, value_t, map_t>::_iterator<iter_value_t>::operator>>(const seq_t& seq) {
  return force_find(seq);
}

template<typename elem_t, typename value_t, template<typename k, typename v> class map_t>
template<typename iter_value_t>
template<typename seq_t>
inline  typename trie<elem_t, value_t, map_t>::template _iterator<iter_value_t>&
trie<elem_t, value_t, map_t>::_iterator<iter_value_t>::insert(const seq_t& seq, const value_t& value) {
  return insert(seq.begin(), seq.end(), value);
}

template<typename elem_t, typename value_t, template<typename k, typename v> class map_t>
template<typename iter_value_t>
template<typename seq_t>
inline typename trie<elem_t, value_t, map_t>::template _iterator<iter_value_t>&
trie<elem_t, value_t, map_t>::_iterator<iter_value_t>::find(const seq_t& seq) {
  return find(seq.begin(), seq.end());
}

template<typename elem_t, typename value_t, template<typename k, typename v> class map_t>
template<typename iter_value_t>
template<typename seq_t>
inline typename trie<elem_t, value_t, map_t>::template _iterator<iter_value_t>&
trie<elem_t, value_t, map_t>::_iterator<iter_value_t>::force_find(const seq_t& seq) {
  return force_find(seq.begin(), seq.end());
}

//@}


/**
 * @name Iterator access
 * Uses a begin and end iterator to define the sequence to operate with.
 */
//@{

template<typename elem_t, typename value_t, template<typename k, typename v> class map_t>
template<typename iter_value_t>
template<typename iter_t>
inline  typename trie<elem_t, value_t, map_t>::template _iterator<iter_value_t>&
trie<elem_t, value_t, map_t>::_iterator<iter_value_t>::insert(const iter_t& begin, const iter_t& end, const value_t& value) {
  force_find(begin, end);
  prefix_m.back()->second.value_m = value;
  return *this;
}

template<typename elem_t, typename value_t, template<typename k, typename v> class map_t>
template<typename iter_value_t>
template<typename iter_t>
inline typename trie<elem_t, value_t, map_t>::template _iterator<iter_value_t>&
trie<elem_t, value_t, map_t>::_iterator<iter_value_t>::find(const iter_t& begin, const iter_t& end) {
  for (iter_t i(begin); valid() && i != end; ++i) {
    get(*i);
  }
  return *this;
}

template<typename elem_t, typename value_t, template<typename k, typename v> class map_t>
template<typename iter_value_t>
template<typename iter_t>
inline typename trie<elem_t, value_t, map_t>::template _iterator<iter_value_t>&
trie<elem_t, value_t, map_t>::_iterator<iter_value_t>::force_find(const iter_t& begin, const iter_t& end) {
  for (iter_t i(begin); i != end; ++i) {
    force(*i);
  }
  return *this;
}

//@}


/**
 * @name Stop-value access
 * Uses a begin iterator and assumes that it can step forward until indicating a supplied value.\n
 * This is useful for C-strings ('\\0' terminated), where the is no way beforehand
 * to determine the end, but where we are certain that a '\\0' character will appear
 * somewhere in the sequence, and signal the end of it.
 */
//@{

template<typename elem_t, typename value_t, template<typename k, typename v> class map_t>
template<typename iter_value_t>
template<typename iter_t>
inline  typename trie<elem_t, value_t, map_t>::template _iterator<iter_value_t>&
trie<elem_t, value_t, map_t>::_iterator<iter_value_t>::insert(const iter_t& begin, const elem_t& last, const value_t& value) {
  force_find(begin, last);
  prefix_m.back()->second.value_m = value;
  return *this;
}

template<typename elem_t, typename value_t, template<typename k, typename v> class map_t>
template<typename iter_value_t>
template<typename iter_t>
inline typename trie<elem_t, value_t, map_t>::template _iterator<iter_value_t>&
trie<elem_t, value_t, map_t>::_iterator<iter_value_t>::find(const iter_t& begin, const elem_t& last) {
  for (iter_t i(begin); valid() && *i != last; ++i) {
    get(*i);
  }
  return *this;
}

template<typename elem_t, typename value_t, template<typename k, typename v> class map_t>
template<typename iter_value_t>
template<typename iter_t>
inline typename trie<elem_t, value_t, map_t>::template _iterator<iter_value_t>&
trie<elem_t, value_t, map_t>::_iterator<iter_value_t>::force_find(const iter_t& begin, const elem_t& last) {
  for (iter_t i(begin); *i != last; ++i) {
    force(*i);
  }
  return *this;
}

//@}






#endif
